package com.geek.spring.sort;

import com.sun.jdi.PathSearchingVirtualMachine;
import org.checkerframework.checker.units.qual.A;
import org.checkerframework.checker.units.qual.K;

import java.lang.annotation.ElementType;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

import static java.util.stream.Collectors.filtering;
import static java.util.stream.Collectors.toList;

/**
 * @program java-spring
 * @description:  排序算法
 * @author: chanzhugang
 * @create: 2021/08/02 17:03
 */
public class SortTest {


    /**
     * O(n^2)
     */

    /**
     * 插入排序1：类似扑克牌，手中牌是有序的，抓到的牌有序插入到手中的牌里
     * 思路：抓到的牌放在末尾，和前面的牌一个个比较找到其正确的位置
     */
    public static int[] insertSort(int[] a) {
        // 2021.8.4
        for (int i = 0; i < a.length; i++) {
            int value = a[i];
            int j = i;
            for (; j > 0 && a[j - 1] > value; j--) {
                // 搬移比抓到的牌大的数据，往后挪
                a[j] = a[j - 1];
            }
            // 抓到的牌放在正确的位置
            a[j] = value;
        }
        return a;
    }


    public static void main(String[] args) {
        int[] a = new int[] {1,9,2,8,3,7};

        int[] result = insertSort0(a);

        for (int i : result) {
            System.out.println(i);
        }
    }

    /**
     *  0819 插入排序
     * @param a
     * @return
     */
    public static int[]  insertSort0(int[] a) {
        // 把元素插入有序数组， 从有序数组最后一个位置开始比较，找到他的位置
        if (a.length <= 1) {
            return a;
        }

        for (int i = 0; i < a.length; i++) {
            int value = a[i];
            int j = i - 1;

            for (; j > 0 && a[j] > value; j--) {
                a[j + 1] = a[j];

            }
            a[j + 1] = value;

           /* for (; j > 0; j--) {
                if (a[j] > value) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = value;*/
        }
        return a;
        
    }

    public void bubbleSort(int[] a) {


    }
    
    

    public static int[] insertSort3(int[] a) {
        // 插入排序：

        // 往有序数组中插入一个值， 保证数组还是有序，

        // 找到这个值所在的位置， 其他值往后挪一位
        if (a.length <=1 ) {
            return a;
        }
        for (int i = 1; i < a.length; i++) {
            int value = a[i];
            int j = i - 1;
            for (; j > 0 && a[j] > value ; j--) {
                a[j + 1] = a[j];
               /* if (a[j] > value) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }*/
            }
            // 把值放在正确的地方
            a[j + 1] = value;
        }
        return a;

    }




    /**
     * 插入排序2：新插入的元素往有序区间里放，并且要保持区间一直有序
     * 从有序区间尾部开始比较，如果满足条件，有序数组元素向后移动，插入位置指针往前偏移，最后赋值
     */
    public static int[] insertSort(int[] a, int n) {
        // 2021.8.4
        if (n <= 1) {
            return a ;
        }
        for (int i = 0; i < n; i++) {
            int value = a[i];
            int j = i - 1;
            for (; j > 0; j--) {
                if (a[j] > value) {
                    // 插入的牌小于手里的牌，手里的牌往后挪
                    a[j + 1] = a[j];
                }
            }
            // 找到正确位置
            a[j + 1] = value;

        }
        return a;
    }

    /**
     * 选择排序： 类似插入排序，将数组分为有序区间和无序区间，
     * 区别是从未排序区间取最小值放在已排序区间末尾（外层循环索引位置）：交换最小值和外层循环索引位置值
     * 选择排序不是稳定排序算法，和最小元素交换后相同元素位置可能发生改变，如：5，8，5，2，1
     */
    public void selectSort(int[] a, int n) {
        // 无序区间找最小值放在有序区间末尾: 本质是交换位置
        if (n <= 1) {
            return;
        }
        for (int i = 0; i < n - 1; i++) {
            int minPos = i;
            for (int j = i; j < n; j++) {
                if (a[j] < a[minPos]) {
                    // 找最小值
                    minPos = j;
                }
            }
            // 交换元素
            int temp = a[i];
            a[i] = a[minPos];
            a[minPos] = temp;
        }
    }


    /**
     * 冒泡排序： 相邻元素比较交换，一次冒泡会让至少一个元素移动到他的正确位置
     * 写操作比较多，不常用
     */
    public void bubbleSort(int[] a, int n) {
        // 2021.8.4
        if (n <= 1) {
            return;
        }
        for (int i = 0; i < n; i++) {
            // 退出循环标志位
            boolean flag = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    // 比较相邻元素
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }


    /**
     * O(nlogn)： 分治策略排序算法
     */

    /**
     *
     * 归并排序: 先拆分、后合并
     * 按中间值拆分成A、B 两个有序数组，再合并成一个有序数组
     */
    public void mergeSort(int[] a) {
        mergeSort(a, 0, a.length);
    }

    private void mergeSort(int[] a, int l, int r) {
        if (r - l <= 1) {
            return;
        }
        int mid = (l + r + 1) / 2;
        // 二分法拆分
        mergeSort(a, l, mid);
        mergeSort(a, mid, r);
        merge(a, l ,mid, r);

    }

    private void merge(int[] a, int l, int mid, int r) {
        // 1,3,5 | 2,4,6
        // 1,2,3,4,5,6
        // 合并两个有序数组，每次比较取最小值
        int[] b = Arrays.copyOfRange(a, l, mid + 1);
        int[] c = Arrays.copyOfRange(a, mid, r + 1);
        // 哨兵优化
        b[b.length - 1] = c[c.length - 1] = Integer.MAX_VALUE;
        // 定义两个数组索引
        int i = 0, j = 0;
        for (int k = l; i < r; k++) {
            if (b[i] < c[j]) {
                a[k] = b[i++];
            } else {
                a[k] = c[j++];
            }
        }
    }


    /**
     * 快速排序：随机取一个数，将小于这个数的值放在左边，大于这个数的值放在右边
     *
     * 方式1：
     */
    public void quickSort(List<Integer> A) {
        qSort(A);
    }

    private List<Integer> qSort(List<Integer> A) {
        if (A.size() <= 1) {
            return A;
        }
        // 随机取一个数：算法导论推荐取第0个数
        int value = A.get(0);
        List<Integer> left = A.stream().filter(a -> a < value).collect(toList());
        List<Integer> mid = A.stream().filter(a -> a == value).collect(toList());
        List<Integer> right = A.stream().filter(a -> a > value).collect(toList());
        // 分治
        left = qSort(left);
        right = qSort(right);
        // 合并
        left.addAll(mid);
        left.addAll(right);
        return left;
    }

    /**
     * 快速排序
     * 方式2: 拆成三部分，小于x的值、 不确定中间状态、 大于x的值。
     * 每一次不确定的值减1；相对的小于x的值会加1或者大于x的值加1
     */
    public void quickSort2(int[] a, int l, int r) {
        if (r - l <= 1) {
            return;
        }
        // 小于x的放左边， 大于x的放右边
        // int x = a[l];
        // i代表x的位置
        int i = partition(a, l, r);
        quickSort2(a, l, i);
        quickSort2(a, i + 1, r);
    }

    private int partition(int[] a, int l, int r) {
        int x = a[l];
        int i = l + 1;
        int j = r;
        while (i != j) { // 中间状态数据为0
            if (a[i] < x) {
                i++;
            } else {
                swap(a, i, --j);
            }
        }
        swap(a, i - 1, l);
        return i-1;

    }

    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }


    /**
     * O(n)
     */

    /**
     * 桶排序： 100万个 0-99之间的数字排序。 相同的数放在同一个桶
     * 设计100个桶，每个桶对应不同的数字，第一个桶全是0， 第100个桶全是99
     */
    public List<Integer> bucketSort(List<Integer> a) {
        // 2021.8.4
        int k = 100;
        List<LinkedList<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            // 创建100个桶
            buckets.add(new LinkedList<>());
        }
        for (Integer item : a) {
            // 将数字放入对应的桶
            buckets.get(item % k).add(item);
        }

        List<Integer> result = new ArrayList<>();
        for (LinkedList<Integer> bucket : buckets) {
            // 将桶里的数字放入列表
            result.addAll(bucket);
        }
        return result;
    }

    // 计数排序

    //基数排序
}